Вот темы задач:
Список тем от Марченкова:
1) определить правоинвариантное отношение эквивалентности, для
которого заданное множество будет являться объединением некоторых
классов эквивалентности;
2) построить регулярное выражение, определяющее заданное множество
слов;
3) построить канонические уравнения для конечного автомата, который
переводит любую двоичную последовательность в заданную периодическую
последовательность;
4) доказать примитивную рекурсивность одноместной функции, отличной
от 0 в двух заданных точках;
5) применить операцию минимизации к заданной частичной функции от
одной переменной (используются вычитание, корни, логарифмы);
6) доказать примитивную рекурсивность одноместной функции, которая
равна числу значений экспоненциально-полиномиальной функции от двух
переменных (например 2^a х 3^b) на отрезке от 0 до х.

Задачи Ложкина

Задача 1 - синтез схем для функций из специальных классов
1) получить нижнюю мощностную оценку функции Шеннона для указанного класса
2) получить верхнюю оценку, совпадающую с нижней

Воспрользоваться утверждением 26.1

Задача 2 - задачу на теорему Храпченко